#include <cstdlib>
#include <iostream>
#include <ctime>
#include "grafo.h"
#include "busqueda_local.h"

using namespace std;

class Grafo leerInput(istream&);
void escribirOutput(ostream&, const vector<uint>&);
timespec diff(timespec start, timespec end);

Grafo leerInput(istream& is, vector<int> &clique) {
	uint n, m;
	is >> n >> m;

	Grafo grafo(n);
	for (int k=0; k < m; k++) {
		uint i, j;
		is >> i >> j;
		grafo.agregarArista(i,j);
	}
	
	is >> n >> m;
	
	for (int k=0; k < n; k++) {
		int i;
		is >> i;
		clique.push_back(i);
	}
	
	return grafo;
}

ostream& operator<<(ostream &os, vector<uint> &solucion) {
	for(vector<uint>::iterator it = solucion.begin(); it != solucion.end(); it++)
		os << (*it) << " ";
	os << endl;
	return os;
}


int main() {

#ifdef TESTING
	timespec start, end, result;
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
#endif

	vector<int> clique;
	Grafo grafo = leerInput(cin, clique);
	//~ CliqueMaximaFronteraExacto iniciar(grafo);
	CliqueMaximaFronteraLocal iniciar(grafo);
	vector<uint> solucion = iniciar.resolver(clique);

#ifdef TESTING
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
	result = diff(start, end);
	cout << result.tv_sec * (unsigned long) 1000000000 + result.tv_nsec << endl;
#endif

#ifndef TESTING
	cout << solucion;
#endif

	return 0;
}

timespec diff(timespec start, timespec end)
{
        timespec temp;
        if((end.tv_nsec - start.tv_nsec) < 0)
        {
                temp.tv_sec = end.tv_sec - start.tv_sec - 1;
                temp.tv_nsec = 1000000000 + end.tv_nsec - start.tv_nsec;
        }
        else
        {
                temp.tv_sec = end.tv_sec - start.tv_sec;
                temp.tv_nsec = end.tv_nsec - start.tv_nsec;
        }
        return temp;
}
